package string

// https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xvn3ke/
// 最长回文子串
// 最直接算法: 遍历所有从起点开始的字符串
// 动态规划: f[n][m] = max(f[n-1][m+1] + 1 && str[n-1] == str[m+1], f[n][m])
// 时间复杂度: O(n^2)
func LongestPalindrome(s string) string {
	lenS := len(s)
	dp := make([][]int, lenS)
	for index := 0; index < lenS; index++ {
		dp[index] = make([]int, lenS)
	}
	maxDp := 0
	maxLeft, maxRight := 0, 0
	for subLen := 1; subLen <= lenS; subLen++ {
		for left := 0; left+subLen-1 < lenS; left++ {
			right := left + subLen - 1
			if 1 == subLen {
				dp[left][right] = 1
			} else if s[left] == s[right] {
				if 2 == subLen {
					dp[left][right] = 2
				} else if dp[left+1][right-1] > 0 {
					dp[left][right] = dp[left+1][right-1] + 2
				}
			}
			if dp[left][right] > maxDp {
				maxDp = dp[left][right]
				maxLeft, maxRight = left, right
			}
		}
	}
	return s[maxLeft : maxRight+1]
}
